#include <stdio.h>
#include <stdlib.h>

int list_length = 0 ;

struct node
{
 int num ;
 struct node *next ;
} ;

void display(struct node *n)
{
 printf("Present list: [") ;
 while(n != NULL)
 {
  printf(" %d", n->num) ;
  n = n->next ;
 }
 printf(" ]\n");
}

struct node *append(struct node *n)
{
 int x ;
 printf("Enter the number: ") ;
 scanf("%d", &x) ;
 if (n == NULL)
 {
  n = malloc(sizeof(struct node));
  n->num = x;
  n->next = NULL;
  list_length++ ;
  return n ;
 }
 else
 {
  struct node *temp, *p ;
  p = n ;
  temp = malloc(sizeof(struct node));
  temp->num = x;
  temp->next = NULL;
  while(p->next!=NULL)
  {
   p = p->next ;
  }
  p->next = temp ;
  list_length++ ;
  return n ;
 }
}

struct node *extend(struct node *n)
{
 int initial, i ;
 struct node *temp= NULL, *p ;
 printf("\nEnter the number of elements in new list: ") ;
 scanf(" %d", &initial) ;
 for(i=0;i<initial;i++)
 {
  printf("\n");
  temp = append(temp) ;
  display(temp);
 }
 p = n ;
 while(p->next != NULL)
 {
  p = p->next ;
 }
 p->next = temp ;
 printf("\nMain list extended!\n") ;
 return n ;
}

struct node *insert(struct node *n)
{
 int index, i, x, flag = 0 ;
 struct node *temp= NULL, *p; 
 printf("\nEnter the index at which you want to insert the number(0-%d): ", list_length) ;
 scanf(" %d",&index) ;
 printf("\nEnter the number: ") ;
 scanf(" %d", &x);
 temp = malloc(sizeof(struct node));
 temp->num = x;
 temp->next = NULL;
 p = n ;
 if(index==0)
 {
  temp->next=p;
  flag=1;
  list_length++;
  return temp;
 }
 else
 {
  for(i=0;;i++)
  {
   if(i==(index-1))
   {
    temp->next=p->next;
    p->next=temp;
    flag=1;
    list_length++;
    break;
   }
   p=p->next;
  }
 }
 if(flag==0)
 {
  printf("\nInvalid Index!!");
 }
 return n;
}

struct node *delete(struct node *n)
{
 struct node *temp= NULL, *p, *current=NULL, *previous=NULL;
 int choice, i, index, x, flag=0;
 printf("\n Delete menu:") ;
 printf("\n 1. Delete by index\n 2. Delete by number") ;
 printf("\n Enter Your Choice(0 to Exit): ") ;
 scanf(" %d",&choice);
 p = n ;
 switch(choice)
 {
  case 1: printf("\nEnter the index which you want to delete(0-%d): ", list_length-1) ;
          scanf(" %d",&index) ;
          if(index==0)
          {
           p=p->next;
           flag=1;
           list_length-- ;
           return p;
          }
          else
          {
           current=p;previous=NULL;
           for(i=1;i<=index;i++)
           {
            previous=current;
            current=current->next;
           }
           previous->next=current->next;
           free(current);
           flag=1;
           list_length-- ;
           return p;
          }
          if(flag==0)
          {
           printf("\nInvalid index!");
           return n;
          }
          break;
  case 2: printf("\nEnter the number which you want to delete: ", list_length-1) ;
          scanf(" %d",&x) ;
          for(current=p,previous=NULL;current!=NULL && (current->num)!=x;previous=current,current=current->next);
          {
           if(current==NULL)
           {
            flag=1;
            return p;
           }
           else
           {
            if(previous==NULL)
            {
             p=p->next;
             flag=1;
             list_length-- ;
             return p;
            } 
            else
            {
             previous->next=current->next;
             free(current);
             flag=1;
             list_length-- ;
             return p;
            }
           }
          }
          if(flag==0)
          {
           printf("\nNumber Not Found!!");
           return n;
          } 
          break;
  default: break;
 }
 return n ;
}

struct node *indexval(struct node *n)
{
 int index, i, x, flag = 0 ;
 struct node *p;
 p=n;
 printf("\nEnter the index(0-%d): ", list_length-1) ;
 scanf(" %d",&index) ;
 if(index==0)
 {
  printf("\n The element at index %d is %d.", index, p->num);
 }
 else
 {
  if(index>0 && index<(list_length-1))
  {
   for(i=0;i<index;i++)
   {
    p = p->next;
   }
   printf("\n The element at index %d is %d.", index, p->num);
  }
  else
  {
   printf("\nInvalid Index!!");
  }
 }
 return n ;
}

struct node *sort(struct node *n)
{
 int i,j,x;
 struct node *p;
 struct node *t;
 p=n;
 for(i=1;i<list_length;i++)
 {
  t=p->next;
  for(j=i+1;j<=list_length;j++)
  {
   if(p->num > t->num)
   {
    x=p->num;
    p->num=t->num;
    t->num=x;
   }
   t=t->next;
  }
  p=p->next;
 }
 return n ;
}


struct node *reverse(struct node *n)
{
 struct node *c,*p,*reversed;
 c = malloc(sizeof(struct node));
 c->num=n->num;
 c->next=NULL;
 p=c;
 n=n->next;
 while(n!=NULL)
 {
  reversed=malloc(sizeof(struct node));
  reversed->num=n->num;
  reversed->next=p;
  p=reversed;
  n=n->next;
 }
 return reversed;
}


void main()
{
 struct node *end = NULL;
 int number, i, initial, choice;
 printf("\nList intialization: ") ;
 printf("\nEnter the number of elements: ") ;
 scanf(" %d", &initial) ;
 for(i=0;i<initial;i++)
 {
  printf("\n");
  end = append(end) ;
  display(end);
 }
 do
 {
  printf("\n\n\t Linked List Menu\n\t==================\n") ;
  printf("\n 1. Append\n 2. Extend\n 3. Insert\n 4. Delete\n 5. Index\n 6. Sort\n 7. Reverse");
  printf("\n Enter Your Choice(0 to Exit): ") ;
  scanf(" %d",&choice);
  switch(choice)
  {
   case 1: end = append(end);
           break;
   case 2: end = extend(end);
           break;
   case 3: end = insert(end);
           break;
   case 4: end = delete(end);
           break;
   case 5: end = indexval(end);
           break;
   case 6: end = sort(end);
           break;
   case 7: end = reverse(end);
           break;
   default: break;
  }
  display(end);
 } while(choice) ;

}
